МІНІСТЕРСТВО ОСВІТИ І НАУКИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення”
на тему:
«Паралельне виконання операцій множення матриць»
Завданння
Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=3П, n2=2І, n3=4Б – КІ-42, де 3П=Ц(300), 2І=А(64), 4Б=Р(159)
n1=300, n2=64, n3=159
Отже маємо матрицю А(300*64) та матрицю В(64*159)
Розробити та описати алгоритм множення матриць А*В на структурі яка задається виразом:
5b-12b-6b-11b-8b-1b-3b-13b – КІ-42, де «nb»- номер букви П.І.Б студента.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
М
А
Ц
Ю
К
Т
А
Р
А
С
І
Г
О
Р
О
В
И
Ч
6
7
1
3
5
4
2
8
Отримаємо – КГТІРМЦО
Для КГТІРМЦО отримаємо 47,74,198,223,93,43,201,250. Даний набір чисел записуємо у стовпець і переводимо у двійкове 8-ми розрядне число:
047 -
00101111
074 -
01001010
198 -
11000110
223 -
11011111
093 -
01011101
043 -
00101011
201 -
11001001
250 -
11111010
В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
0
0
1
0
1
1
1
1
=>
0
0
1
0
1
1
1
1
0
1
0
0
1
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
1
1
1
1
1
1
1
0
0
1
1
1
1
0
1
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
1
0
0
1
0
1
0
1
1
1
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує конкретну 8-ми процесорну систему (структуру) із напрявленими зв’язками між вершинами.
Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
Zi=1009587, n=7
type=1(спільна пам’ять)
3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW:
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
tU=(Zk-3 +1)tS=(Zk-2 +1)tP=(Zk-1 +1)tZ=(Zk+1)tW, де Zi відповідна цифра номера залікової книжки, k -кількість цифр в номері залікової книжки.
tU=10tS=1tP=9tZ=4tW
Анотація
В даній курсовій роботі було розроблено програму для множення двох матриць розміром 190*216 та 216*73 на восьми процесорах, з заданою структурою зв’язків. Завантаження даних в процесори відбувається через спільну пам’ять. Також було розроблено функціональну схему і визначено основні характеристики розробленого паралельного алгоритму. Для реалізації паралельного алгоритму множення матриць було використано інтерфейс передачі повідомлень (МРІ) між процесами, оскільки він має широкі можливості. Для програмної реалізації алгоритму було обрано мову С++, з використанням MPI. Наведені граф-схеми виконання алгоритму, схеми планування обчислень і блок-схеми програми множення матриць пояснюють реалізацію даного алгоритму більш детально.
Аnnotation
In this term paper has developed a program to multiply two matrices of size 300 * 64 and 64 * 159 on eight processors of a given structure relationships. Loading data into the processor takes place through shared memory. They also developed a functional diagram and the main characteristics of the developed parallel algorithm . To implement the parallel matrix multiplication algorithm used message passing interface ( MPI ) ...
